#include "BinaryTree.h"
#include "Queue.h"
#define _CRT_SECURE_NO_WARNINGS 1

BTNode* BuyNewNode(BTDataType a)
{
	BTNode* newNode = (BTNode*)malloc(sizeof(BTNode));
	if (!newNode)
	{
		perror("Malloc fail");
		return NULL;
	}
	newNode->_data = a;
	newNode->_left = NULL;
	newNode->_right = NULL;

	return newNode;
}

BTNode* BinaryTreeCreate(BTDataType* a, int n, int* pi)
{
	if (a[*pi] == '#')
	{
		(*pi)++;
		return NULL;
	}
	if (*pi >= n) return NULL;

	BTNode* ret = BuyNewNode(a[(*pi)++]);
	if (!ret)
	{
		perror("malloc fail");
		return NULL;
	}
	ret->_left = BinaryTreeCreate(a, n, pi);
	ret->_right = BinaryTreeCreate(a, n, pi);

	return ret;
}

void BinaryTreeDestory(BTNode** root)
{
	assert(root);
	if ((*root)) return;

	BinaryTreeDestory(&((*root)->_left));
	BinaryTreeDestory(&((*root)->_right));
	free(*root);
	*root = NULL;
}

int BinaryTreeSize(BTNode* root)
{
	if (!root) return 0;

	return BinaryTreeSize(root->_left) + BinaryTreeSize(root->_right) + 1;
}

int BinaryTreeLeafSize(BTNode* root)
{
	if (!root) return 0;
	if (!root->_left && !root->_right) return 1;

	return BinaryTreeLeafSize(root->_left) + BinaryTreeLeafSize(root->_right);
}

int BinaryTreeLevelKSize(BTNode* root, int k)
{
	if (!root) return 0;
	if (k == 1) return 1;

	return BinaryTreeLevelKSize(root->_left, k - 1) + BinaryTreeLevelKSize(root->_right, k - 1);
}

BTNode* BinaryTreeFind(BTNode* root, BTDataType x)
{
	if (!root) return NULL;
	if (root->_data == x)
		return root;
	BTNode* bt = BinaryTreeFind(root->_left, x);
	if (bt) return bt;
	else return BinaryTreeFind(root->_right, x);
}

void BinaryTreePrevOrder(BTNode* root)
{
	if (!root) return;

	printf("%c ", root->_data);

	BinaryTreePrevOrder(root->_left);
	BinaryTreePrevOrder(root->_right);
}

void BinaryTreeInOrder(BTNode* root)
{
	if (!root) return;

	BinaryTreeInOrder(root->_left);
	printf("%c ", root->_data);
	BinaryTreeInOrder(root->_right);
}

void BinaryTreePostOrder(BTNode* root)
{
	if (!root) return;

	BinaryTreePostOrder(root->_left);
	BinaryTreePostOrder(root->_right);

	printf("%c ", root->_data);
}

void BinaryTreeLevelOrder(BTNode* root)
{
	Queue q;
	QueueInit(&q);
	QueuePush(&q, root);
	while (!QueueEmpty(&q))
	{
		BTNode* p = QueueFront(&q);
		QueuePop(&q);
		if (p->_left) QueuePush(&q, p->_left);
		if (p->_right) QueuePush(&q, p->_right);

		printf("%c ", p->_data);
	}
	puts(" ");
}

bool BinaryTreeComplete(BTNode* root)
{
	Queue q;
	QueueInit(&q);
	QueuePush(&q, root);
	bool flag = false;
	while (!QueueEmpty(&q))
	{
		int sz = QueueSize(&q);
		for (int i = 0; i < sz; i++)
		{
			BTNode* p = QueueFront(&q);
			QueuePop(&q);

			if (!p) flag = true;
			else
			{
				if (flag) return false;
				QueuePush(&q, p->_left);
				QueuePush(&q, p->_right);
			}
		}
	}
	return true;
}
